package formal.graph;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author DengYuan2
 * @create 2021-02-10 19:20
 */
public class M_785 {
    public static void main(String[] args) {
        int[][] graph = {
                {1, 2, 3},
                {0, 2},
                {0, 1, 3},
                {0, 2}
        };
//        int[][] graph = {{1,3}, {0,2}, {1,3}, {0,2}};
        boolean res = isBipartite(graph);
        System.out.println(res);
    }


    public static int UNCOLOURED = 0;
    public static int red = 1;
    public static int green = 2;


    /**
     * 我的想法：相邻的两个数组之间没有交集
     * 但是不对，比如说这个：[[4,1],[0,2],[1,3],[2,4],[3,0]]，应该是false
     * <p>
     * 官方-分红绿两色-广度优先
     *
     * @param graph
     * @return
     */
    public static boolean isBipartite(int[][] graph) {
        int len = graph.length;
        int[] color = new int[len];
        //这个for循环是针对不连通图的
        for (int i = 0; i < graph.length; i++) {
            if (color[i] == UNCOLOURED) {
                Queue<Integer> queue = new LinkedList<>();
                queue.offer(i);
                color[i] = red;
                while (!queue.isEmpty()) {
                    Integer poll = queue.poll();
                    int other = (color[poll] == red) ? green : red;
                    for (int num : graph[i]) {
                        if (color[num] == UNCOLOURED) {
                            color[num] = other;
                            queue.offer(num);
                        } else if (color[num] != other) {
                            return false;
                        }
                    }
                }
            }
        }
        return true;
    }

    public static boolean isValid = true;
    public static int[] color;

    /**
     * 官方-深度优先
     *
     * @param graph
     * @return
     */
    public static boolean isBipartite2(int[][] graph) {
        color = new int[graph.length];
        for (int i = 0; i < graph.length; i++) {
            if (color[i] == UNCOLOURED) {
                helper(graph, i, red);
            }
        }
        return isValid;
    }

    public static void helper(int[][] graph, int node, int cur) {
        color[node] = cur;
        int other = (cur == red) ? green : red;
        for (int num : graph[node]) {
            if (color[num] == UNCOLOURED) {
                helper(graph, num, other);
                if (!isValid) {
                    return;
                }
            } else if (color[num] != other) {
                isValid = false;
                return;
            }
        }

        return;
    }
}
